Huffman Tree

发表于 | 更新于: | 分类于 ， | | 阅读数
字数统计: 684 | 阅读时长 ≈ 3

霍夫曼树的定义、实现及霍夫曼编码的求解与输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;

struct HTNode {
	int weight;//权值
	int parent;//指向父结点的指针域
	int lchild;//左指针域
	int rchild;//右指针域
};

class huffman_BT {
private:
	HTNode *bt;
	char **hc;
	int nn;
public:
	void select(HTNode *p, int k, int *i, int *j);
	void creat_hufm_BT();
	int HuffmanCoding();
	void HuffmanDisplay();
};
//在前k-1个结点中选择权值最小的两个结点i和j
void huffman_BT::select(HTNode *p, int k, int *i, int *j) {
	int w, n = 0;
	while (n < k && (p + n)->parent != -1) n++;//寻找指向父结点指针为空的起始结点
	w = (p + n)->weight;
	*i = n;
	while (n < k) {
		if ((((p + n)->weight) < w) && ((p + n)->parent == -1)) *i = n, w = (p + n)->weight;
		n++;
	}
	n = 0;
	while ((n < k) && ((p + n)->parent != -1) || (n == (*i))) n++;
	w = (p + n)->weight;
	*j = n;
	while (n < k) {
		if (((p + n)->weight < w) && (n != (*i)) && ((p + n)->parent == -1)) {
			*j = n;
			w = (p + n)->weight;
		}
		n++;
	}
	if ((*i) < (*j)) n = (*i), *i = *j, *j = n;
}

void huffman_BT::creat_hufm_BT() {
	HTNode *p;
	int k, i, j, m;
	cout << "请输入结点的个数：";
	cin >> nn;
	m = nn * 2 - 1;
	bt = new HTNode[m];
	p = bt;
	for (i = 0; i < m; i++) {
		p[i].weight = 0;
		p[i].parent = -1;
		p[i].lchild = -1;
		p[i].rchild = -1;
	}
	cout << "请依次输入权值：" << endl;
	for (i = 0; i < nn; i++) {
		cout << "请输入第" << i + 1 << "个权值：";
		cin >> p[i].weight;
	}
	for (k = nn; k < m; k++) {
		select(p, k, &i, &j);
		(p + i)->parent = k;
		(p + j)->parent = k;
		(p + k)->lchild = i;
		(p + k)->rchild = j;
		(p + k)->weight = (p + i)->weight + (p + j)->weight;
	}
}
//从叶子到根逆向求每个字符的霍夫曼编码
int huffman_BT::HuffmanCoding() {
	char *cd = new char[nn];
	int start, c, f;
	hc = new char*[nn];
	cd[nn - 1] = '\0';
	for (int i = 0; i < nn; i++) {
		start = nn - 1;
		for (c = i, f = bt[i].parent; f != -1; c = f, f = bt[f].parent) {
			if (bt[f].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		}
		hc[i] = new char[nn - start];
		strcpy(hc[i], &cd[start]);
	}
	return 1;
}
//霍夫曼编码信息输出
void huffman_BT::HuffmanDisplay() {
	HTNode *p;
	int k;
	p = bt;
	cout << "k" << setw(7) << "weight" << setw(7) << "parent" << setw(7) << "lchild" << setw(7) << "rchild" << endl;
	for (k = 0; k < 2 * nn - 1; k++) {
		cout << k << setw(7) << (p + k)->weight << setw(7) << (p + k)->parent << setw(7) << (p + k)->lchild << setw(7) << (p + k)->rchild << endl;
	}
	cout << "霍夫曼编码为：" << endl;
	for (k = 0; k < nn; k++) {
		cout << char('A' + k) << "(权值：" << p[k].weight << "):" << hc[k] << endl;
	}
}

int main() {
	huffman_BT hbt;
	hbt.creat_hufm_BT();
	hbt.HuffmanCoding();
	hbt.HuffmanDisplay();
	return 0;
}